package Classic150;

public class 加油站 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        /*
            题目保证了答案唯一，即只有从解对应的加油站出发才能再回到出发点
            base：假设加油站B是解出发点，在它之前如果存在一个加油站A可以正常开到加油站B，
            则加油站A也可以是解出发点，与题目矛盾
            解出发点要满足的性质：
            1、从解出发点获得的汽油比去下一站消耗的汽油更多
            2、从解出发点出发可以正常开到中途任何一个加油站
            通过性质2再加上base可以得出：从解出发点出发到任何一个加油站，剩余的油量比从别的加油站出发都多
            通过这个结论，我们可以比较从每个加油站出发到数组最后一个加油站之后剩余的油量，最多的那个就是解出发点
            此外，如果gas的总和小于cost的总和，那么无论从哪里出发，一定回不到出发点，可以通过在上面的比较过程中完成判断（从第一个加油站出发到最后一个加油站之后的剩余油量即是）
         */
        int aftSum = 0;
        int start = 0;
        int max = Integer.MIN_VALUE;
        for (int i = gas.length - 1; i >= 0; i--) {
            aftSum += gas[i] - cost[i];
            if (aftSum > max) {
                start = i;
                max = aftSum;
            }
        }
        if (aftSum < 0) return -1;
        return start;
    }
}
